package com.sympsel.Optimal_Algorithm_OA;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;


/**
 * 分治算法
 */
public class DivideAndConquerAlgorithm {
    public void sortColors(int[] nums) {
        int left = 0, right = nums.length - 1;
        for (int i = 0; i <= right; ) {
            if (nums[i] == 0) {
                swap(nums, i++, left++);
            } else if (nums[i] == 1) {
                i++;
            } else {
                swap(nums, i, right--);
            }
        }
    }

    private void swap(int[] arr, int i, int j) {
        if (i != j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    @Test
    public void test1() {
        int[] nums = {2, 0, 2, 1, 1, 0};
        sortColors(nums);
        System.out.println(Arrays.toString(nums));
    }

    private void quickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int key = nums[new Random().nextInt(right - left + 1) + left];
        int l = left;
        int r = right;
        for (int i = left; i <= r; ) {
            if (nums[i] < key) {
                swap(nums, i++, l++);
            } else if (nums[i] == key) {
                i++;
            } else {
                swap(nums, i, r--);
            }
        }
        quickSort(nums, left, l - 1);
        quickSort(nums, r + 1, right);
    }

    public void quickSort(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
    }

    @Test
    public void test2() {
        int[] nums = {5, 2, 3, 1};
        quickSort(nums);
        System.out.println(Arrays.toString(nums));
    }

    public int findKthLargest(int[] nums, int k) {
        return halfQuickSort(nums, 0, nums.length - 1, k);
    }

    private int halfQuickSort(int[] arr, int begin, int end, int k) {
        int key = arr[new Random().nextInt(end - begin + 1) + begin];
        int left = begin, right = end;
        for (int i = begin; i <= right; ) {
            if (key < arr[i]) {
                swap(arr, i, right--);
            } else if (key == arr[i]) {
                i++;
            } else {
                swap(arr, i++, left++);
            }
        }
        if (end - right >= k) {
            return halfQuickSort(arr, right + 1, end, k);
        }
        if (end - left + 1 >= k) {
            return key;
        }
        return halfQuickSort(arr, begin, left - 1, k - (end - left + 1));
    }

    @Test
    public void test3() {
        int[] nums = {3, 2, 1, 5, 6, 4};
        System.out.println(findKthLargest(nums, 2));
    }

    @Test
    public void test4() {
        int[] nums = {3, 2, 3, 1, 2, 4, 5, 5, 6};
        System.out.println(findKthLargest(nums, 4));
    }

    public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
        if (k == 0) {
            return ret;
        }
        halfQuickSort(arr, 0, arr.length - 1, k, ret);
        return ret;
    }

    private int halfQuickSort(int[] arr, int begin, int end, int k, int[] ret) {
        int key = arr[new Random().nextInt(end - begin + 1) + begin];
        int left = begin, right = end;
        for (int i = begin; i <= right; ) {
            if (key > arr[i]) {
                swap(arr, i++, left++);
            } else if (key == arr[i]) {
                i++;
            } else {
                swap(arr, i, right--);
            }
        }
        if (left - begin >= k) {
            return halfQuickSort(arr, begin, left - 1, k, ret);
        }

        if (right - begin + 1 >= k) {
            for (int i = 0; i < ret.length; i++) {
                ret[i] = arr[i];
            }
            return key;
        }

        return halfQuickSort(arr, right + 1, end, k - (right - begin + 1), ret);
    }

    @Test
    public void test5() {
        int[] arr = {3, 5, 1, 6, 2, 7, 4};
        int[] ret = smallestK(arr, 4);
        System.out.println(Arrays.toString(ret));
    }

    // 归并排序
    public void mergeSort0(int[] nums) {
        int[] temp = new int[nums.length];
        mergeSort(nums, 0, nums.length - 1, temp);
    }

    private void mergeSort0(int[] nums, int begin, int end, int[] temp) {
        if (begin >= end) {
            return;
        }
        int mid = (end - begin) / 2 + begin;
        mergeSort(nums, begin, mid, temp);
        mergeSort(nums, mid + 1, end, temp);

        int left = begin, right = mid + 1, index = 0;
        while (left <= mid && right <= end) {
            temp[index++] = nums[left] < nums[right] ? nums[left++] : nums[right++];
        }
        while (left <= mid) {
            temp[index++] = nums[left++];
        }
        while (right <= end) {
            temp[index++] = nums[right++];
        }

        for (int i = begin; i <= end; i++) {
            nums[i] = temp[i - begin];
        }
    }

    @Test
    public void test6() {
        int[] nums = {5, 2, 3, 1, 4, 5, 7, 4, 2, 8, 6};
        mergeSort0(nums);
        System.out.println(Arrays.toString(nums));
    }

    public int reversePairs(int[] record) {
        int len = record.length;
        if (len < 2) {
            return 0;
        }
        int[] arr = new int[len];
        return mergeSort(record, 0, len - 1, arr);
    }

    private int mergeSort(int[] record, int begin, int end, int[] arr) {
        if (begin >= end) {
            return 0;
        }
        int mid = (end - begin) / 2 + begin;
        int ret = mergeSort(record, begin, mid, arr) + mergeSort(record, mid + 1, end, arr);
        int i = begin, j = mid + 1, index = begin;
        while (i <= mid && j <= end) {
            if (record[i] > record[j]) {
                ret += mid + 1 - i;
                arr[index++] = record[j++];
            } else {
                arr[index++] = record[i++];
            }
        }
        while (i <= mid) {
            arr[index++] = record[i++];
        }

        while (j <= end) {
            arr[index++] = record[j++];
        }

//        for (int k = begin; k <= end; k++) {
//            record[k] = arr[k];
//        }

        System.arraycopy(arr, begin, record, begin, end - begin + 1);

        return ret;
    }

    @Test
    public void test7() {
        int[] record = {7, 5, 6, 4};
        System.out.println(reversePairs(record));
        System.out.println(reversePairs(new int[]{4, 5, 6, 7}));
        record = new int[]{7, 5, 6, 4, 9};
        System.out.println(reversePairs(record));
        System.out.println(reversePairs(new int[]{4, 5, 6, 7, 9}));
    }

    private void mergeSort(int[] nums, int begin, int end, int[] tempNums, int[] tempIndex, int[] indexs, int[] ret) {
        if (begin >= end) return;
        int mid = (end - begin) / 2 + begin;
        mergeSort(nums, begin, mid, tempNums, tempIndex, indexs, ret);
        mergeSort(nums, mid + 1, end, tempNums, tempIndex, indexs, ret);

        int i = begin, j = mid + 1, index = begin;

        while (i <= mid && j <= end) {
            if (nums[i] > nums[j]) {
                tempNums[index] = nums[j];
                tempIndex[index++] = indexs[j++];
            } else {
                ret[indexs[i]] += (j - 1) - mid;
                tempNums[index] = nums[i];
                tempIndex[index++] = indexs[i++];
            }
        }

        while (i <= mid) {
            ret[indexs[i]] += end - mid;
            tempNums[index] = nums[i];
            tempIndex[index++] = indexs[i++];
        }

        while (j <= end) {
            tempNums[index] = nums[j];
            tempIndex[index++] = indexs[j++];
        }

        for (int k = begin; k <= end; k++) {
            nums[k] = tempNums[k];
            indexs[k] = tempIndex[k];
        }
    }

    public List<Integer> countSmaller(int[] nums) {
        int len = nums.length;
        if (len < 2) {
            return new ArrayList<>() {{
                int lenCopy = len;
                while (lenCopy-- > 0) {
                    add(0);
                }
            }};
        }
        int[] tempNums = new int[len];
        int[] tempIndex = new int[len];
        int[] indexs = new int[len];
        for (int i = 0; i < len; i++) {
            indexs[i] = i;
        }
        int[] ret = new int[len];
        mergeSort(nums, 0, len - 1, tempNums, tempIndex, indexs, ret);
        return new ArrayList<>() {{
            for (int i = 0; i < len; i++) {
                add(ret[i]);
            }
        }};
    }

    @Test
    public void test8() {
        int[] nums = {5, 2, 6, 1};
        System.out.println(countSmaller(nums));
    }

    private int[] temp;

    private int mergeSort(int[] nums, int begin, int end) {
        if (begin >= end) {
            return 0;
        }

        int mid = (end - begin) / 2 + begin;
        int ret = mergeSort(nums, begin, mid) + mergeSort(nums, mid + 1, end);
        int i = begin, j = mid + 1, index = begin;
        while (i <= mid && j <= end) {
            if (nums[i] > nums[j] * 2) {
                ret += j - 1 - mid;
            }

            if (nums[i] <= nums[j]) {
                temp[index++] = nums[i++];
            } else {
                temp[index++] = nums[j++];
            }
        }

        while (i <= mid) {
            temp[index++] = nums[i++];
        }

        while (j <= end) {
            if (nums[i] > nums[j] * 2) {
                ret += j - 1 - mid;
            }
            temp[index++] = nums[j++];
        }

        for (int k = begin; k <= end; k++) {
            nums[k] = temp[k];
        }

        return ret;
    }

    public int reversePairs1(int[] nums) {
        int len = nums.length;
        if (len < 2) {
            return 0;
        }
        temp = new int[len];
        return mergeSort(nums, 0, len - 1);
    }

}

class Solution {
    private int[] temp;

    private int mergeSort(int[] nums, int begin, int end) {
        if (begin >= end) {
            return 0;
        }

        int mid = (end - begin) / 2 + begin;
        int ret = mergeSort(nums, begin, mid) + mergeSort(nums, mid + 1, end);
        int i = begin, j = mid + 1, index = begin;
        // 合并前统计反转对
        while (i <= mid) {
            while (j <= end && (long)nums[i] > (long)nums[j] * 2) {
                j++;
            }
            ret += j - 1 - mid;
            i++;
        }
        // 执行合并操作
        i = begin;
        j = mid + 1;
        while (i <= mid && j <= end) {
            if (nums[i] <= nums[j]) {
                temp[index++] = nums[i++];
            } else {
                temp[index++] = nums[j++];
            }
        }

        while (i <= mid) {
            temp[index++] = nums[i++];
        }

        while (j <= end) {
            temp[index++] = nums[j++];
        }

        for (int k = begin; k <= end; k++) {
            nums[k] = temp[k];
        }

        return ret;
    }

    public int reversePairs(int[] nums) {
        int len = nums.length;
        if (len < 2) {
            return 0;
        }
        temp = new int[len];
        return mergeSort(nums, 0, len - 1);
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.reversePairs(new int[]{
//                2, 4, 3, 5, 1
                1, 3, 2, 3, 1
        }));
    }
}
